1. Field of the Invention
The present invention generally relates to a method and an apparatus for multicast packet readout control, and more particularly, to a technique for reading and transmitting packets from a packet buffer, while performing QoS (Quality of Service) processing (including bandwidth control and priority routing control), in a layer 2 switch in IP (Internet Protocol) network. The packet buffer temporarily stores packets, such as Ether (registered trademark) frames, for each destination.
2. Description of the Related Art
A unicast packet addressed to a single destination is read from a packet buffer and transmitted to the destination. For a multicast packet with multiple destinations, the packet read from the packet buffer has to be copied as many as the number of destinations so as to be transmitted to each of the destinations.
To identify the destinations of a multicast packet, a destination bitmap is used, in which each destination is represented by one bit. The number of bits used in the destination bitmap agrees with the acceptable maximum number of destination in the multicasting scheme. The destination bitmap is managed under the domain ID, and each domain is associated with the corresponding destination bitmap in a table. This table is referred to as a domain group table.
When transmitting a multicast packet, the domain ID attached to the multicast packet is used as the address for accessing the domain group table. The destination bitmap managed under this domain ID is acquired from the table. The multicast packet is then copied and transmitted to all the destinations indicated by the bit positions of “1” in the bitmap.
FIG. 1A and FIG. 1B illustrate a multicast packet format and the structure of a domain group table, respectively. As illustrated in FIG. 1A, a domain ID is prepended to the multicast packet. Based on this domain ID, the domain group table shown in FIG. 1B is read, and the destination bitmap is acquired. The multicast address is transmitted to those destinations indicated by the entries with a bit “1” set in the destination bitmap. In the example shown in FIG. 1A, 256 destinations are recorded in each bitmap in the table.
FIG. 2 is a functional block diagram of the conventional multicast packet readout control apparatus, and FIG. 3 is a time chart of the multicast packet readout control apparatus. The multicast packet readout control apparatus includes a scheduler 10, a packet buffer controller 20, a multicast temporary buffer 50, a bandwidth control table 60, and blocks A, B, and C (which are structured as programmable LSI circuits, such as FPGAs). The control apparatus also includes a packet buffer 30 and a domain group table 40, which are implemented as memories connected externally to the main body of the control apparatus.
The conventional multicast packet readout control procedure is described below. The parenthesized numerical symbols inserted in FIG. 2 and FIG. 3 correspond to the step numbers described below.    (1) The packet buffer controller 20 writes the input multicast packet in packet buffer 30.    (2) Th packet buffer controller 20 informs to the scheduler 10 that the multicast packet has been written in the packet buffer 30 (occupied or non-empty state).    (3) The scheduler 10 supplies a multicast packet reading request to the packet buffer controller 20.    (4) The packet buffer controller 20 reads the header of the multicast packet from the packet buffer 30.    (5) The packet buffer controller 20 controls block A so as to access the associated domain group table 40 based on the domain ID information written in the header of the multicast packet.    (6) Block A acquires the multicast destination bitmap from the domain group table 40, and transmit the multicast destination bitmap to the scheduler 10.    (7) The scheduler 10 selects a destination to which output bandwidth is allocated from among those destinations with a bit “1” in the multicast destination bitmap, and supplies a multicast packet readout request to the packet buffer controller 20.    (8) The packet buffer controller 20 reads the header and the data portion of the multicast packet from the packet buffer 30.    (9) The packet buffer controller 20 sends the multicast packet read from the packet buffer 30 to the destination selected in step (7) via block B, and simultaneously, stores this multicast packet in the multicast temporary buffer 50.    (10) The packet buffer controller 20 supplies a readout completion notice, which indicates that the reading of the multicast packet from the packet buffer 30 has been completed, to the scheduler 10.    (11) The scheduler 10 selects the next destination to which output bandwidth is allocated from those destinations with a bit “1” in the multicast destination bitmap, and instructs block B to read the multicast packet from the multicast temporary buffer 50.    (12) Block B reads the multicast packet from the multicast temporary buffer 50 and transmits the multicast packet to the destination selected in step (11).    (13) Block B reads the multicast packet from the multicast temporary buffer 50 at an interval of unicast packet readout periods for reading unicast packets from the packet buffer 30.    (14) Subsequently, the above-described steps (11) through (13) are repeated for the remaining destinations with a bit “1” until the multicast packet is transmitted to all the destinations set in the multicast destination bitmap. When the transmission of the multicast packet to all the destinations is completed, the next multicast packet stored in the packet buffer 30 is transmitted to the destinations by performing the above-described procedure.
FIG. 3 is a time chart showing the above-described procedure along the time axes. In FIG. 3, a1, b1, c1, a2, b2, and c2 denote unicast packets, mc1 and mc2 denote multicast packets, and m denotes the header portion of the multicast packet mc1. Symbol A denotes the destination ports of packets a1 and a2, B denotes the destination ports of packets b1 and b2, C denotes the destination ports of packets c1 and c2.
FIG. 4 is a functional block diagram illustrating a conventional multicast packet readout control. In FIG. 4, the multicast destination bitmap 11 is acquired from the domain group table 40. The bandwidth allocation table 16 is installed through software processing, which table records bandwidths of users allocated by contract. The bandwidth control unit 13 periodically adds the bandwidth set in the bandwidth allocation table 16 to the bandwidth of each user. When the packet is output to the destination, the amount of packet is subtracted from the bandwidth. If the subtraction result is positive, the next packet can be output.
In the empty flag setting unit 12 is set a flag indicating whether packets are delayed in the packet buffer 30. The flag is set for each of the destination ports. The readout queue selector 15 selects a destination from those destinations that exhibit positive values of bandwidth and have flags indicating the non-empty state (that is, the accumulation of packets in the packet buffer 30), and informs the selected queue to the readout address generator 21. The readout address generator 21 generates a packet readout address indicating the address in the packet buffer 30, from which the packet is to be read out.
The readout queue selector 15 determines whether a unicast packet or a multicast packet is to be transmitted to the selected destination. According to the determination result, the readout queue selector 15 controls the selector 70 so as to output either one of the unicast packet from the packet buffer 30 and the multicast packet from the multicast temporary buffer 50.
To read and transmit packets from the packet buffer 30 or the multicast temporary buffer 50, the following conditions have to be satisfied.                Output bandwidth has been allocated to the destination port under bandwidth control; and        The empty flag indicates the non-empty state (with packets accumulated in the packet buffer 30), or the entry of the muticast destination bitmap is still set to “1” because of existence of multicast packets in the multicast temporary buffer 50.        
The readout queue selector 15 selects a destination from those destinations that meet with the conditions, and reads the packet from the packet buffer 30 or the multicast temporary buffer 50. Concerning multicast packets, they are reads from the packet buffer 30, and stored temporarily in the multicast temporary buffer 50. If the above-described conditions are satisfied, multicast packets are read and transmitted from the multicast temporary buffer 50.
The multicast packet stored in the multicast temporary buffer 50 is copied and transmitted to all the destinations with a bit “1” set in the multicast destination bitmap 11. After the multicast packet has been copied and transmitted to all the destinations, the next multicast packet is read from the packet buffer 30, stored in the multicast temporary buffer 50, and transmitted to the destinations through the same process.
If there is any single destination to which port output bandwidth has not been allocated among those destinations with a bit “1” in the multicast destination bitmap 11, the transmission process of this multicast packet is not completed, and therefore, the next multicast packet cannot be output.
To overcome this problem, the scheduler 10 is furnished with a discard timer 14. If copies of the multicast packet are not transmitted to all the destinations within a prescribed time period, the multicast packet is discarded so as to allow the next multicast packet to be read form the packet buffer 30 and subjected to the transmission process.
With the conventional multicast packet readout control, class priority judgment or strict priority control (SP control) affects the multicast packet readout operation. Explanation is made of the influence below. Based on the acquired destination bitmap information, the scheduler 10 supplies a multicast packet readout request to the packet buffer controller 20 or the multicast temporary buffer 50 (in above-described steps (7) or (11)). At this time, the scheduler 10 performs request acceptability judgment, as follows:                Determination as to availability of allocatable output bandwidth under bandwidth control (through periodical addition of bandwidth using a token and subtraction of bandwidth during the packet reading operation);        Determination of the empty flag value (indicating whether there are packets accumulated in the packet buffer 30); and        Logical determination for selection of readout available queue (selection of destination port by weighted round-robin control and class priority (SP) judgment).        
In class priority (SP) judgment, class with higher priority is selected from the selectable packets. Priority classes include the followings, which are listed from the higher order.    [1] unicast highest priority class (Uni-H Class)    [2] Unicast high priority class (Uni-M Class)    [3] Multicast high priority class (Mul-H Class)    [4] Unicast low priority class (Uni-L Class)    [5] Multicast low priority class (Mul-L Class)
It should be noted that the class priority (SP) judgment is closed in each destination port.
Actual example of influence of class priority (SP) judgment on multipacket readout control is explained with reference to FIG. 5. It is assumed that, in the request acceptability determination performed by the scheduler 10, output bandwidth is allocated sufficiently to all the destination ports (ports A, B, and C in FIG. 5). It is also assumed that, concerning determination as to the presence of packets, high-priority class multicast packets (PACKET i and PACKET ii in Mul-H class) are accumulated in packet buffer 30, designating destination ports A, B, and C. It is further assumed that a large number of unicast packets of highest priority class (Uni-H class) have been input to a certain port (for example, Port A) among the designated designation ports A, B, and C.
Under these circumstances, multicast packet readout control is performed as follows. The step numbers below correspond to the parenthesized numerical symbols shown in FIG. 2 and FIG. 3.    (1) Multicast packets (PACKET i and subsequent PACKET ii) are stored in packet buffer 30. At this time, unicast packets of the highest priority class for destination port A are also stored in packet buffer 30.    (2) The scheduler 10 is informed of the writing of multicast packet (PACKET i) in the packet buffer 30.    (3) The scheduler 10 supplies a multicast readout request to the packet buffer controller 20.    (4) The packet buffer controller 20 reads the header of the multicast packet (PACKET i) from the packet buffer 30.    (5) The associated multicast destination bitmap for PACKET i is read from the domain group table 40 based on the domain ID information written in the header.    (6) The multicast destination bitmap acquired from the domain group table 40 is transmitted to the scheduler 10.    (7) The scheduler 10 selects a multicast packet (for example, PACKET i) with a bit “1” set in the multicast destination bitmap designating a destination port (A, B, or C) to which output bandwidth is allocated, or a unicast packet of the highest priority class at destination port A, based on the weighed round-robin method and class priority (SP) judgment. For example, the scheduler 10 supplies a readout request for the unicast packet of highest priority class at destination port A to the packet buffer controller 20 to allow the unicast packet to be read and transmitted to the destination. Then, the scheduler 10 outputs a readout request for the multicast packet for destination port B for transmission of this multicast packet, and deletes “1” from port B in the destination bitmap. The remaining destinations of the multicast packet are those defined by destination ports A and C.    (8) The packet buffer controller 20 reads the header and the data portion of the multicast packet (PACKET i) from the packet buffer 30.    (9) The multicast packet (PACKET i) read from the packet buffer 30 is output to the destination port B determined in step (7), and at the same time, stored in the multicast temporary buffer 50.    (10) The packet buffer controller 20 supplies a readout completion notice, indicating that the reading of the multicast packet (PACKET i) from the packet buffer 30 has been completed, to the scheduler 10.    (11) The scheduler 10 selects a multicast packet (for example, PACKET i) with a bit “1” set in the multicast destination bitmap for a remaining port (A or C) to which output bandwidth is allocated, or a unicast packet of the highest priority class at destination port A, based on the weighed round-robin method and class priority (SP) judgment. For example, the scheduler 10 outputs a readout request for the multicast packet for destination port C to the multicast temporary buffer 50, and deletes “1” from port C in the destination bitmap after the transmission of this multicast packet. The remaining destination of the multicast packet is that defined by destination ports A.    (12) The multicast packet (PACKET i) read from the multicast temporary buffer 50 is output to the destination port C selected in step (11).    (13) After the multicast packet (PACKET i) has been transmitted, a transmission completion notice is supplied to the scheduler 10.    (14) Subsequently, the above-described steps (11) through (13) are repeated for the remaining destinations with a bit “1” until the multicast packet (PACKET i) is transmitted to all the destinations set in the multicast destination bitmap. It should be noted that if destination port A that stores the highest-priority unicast packets (determined by SP control) still remains in the remaining destination, then priority is given to the readout of this unicast packet at destination port A, while withholding transmission of a multicast packet from the destination port A.With this conventional arrangement, the readout queue selector 15 does not select a multicast packet of high priority class (Mul-H class) for destination port A until there is no unicast packet of the highest priority class (Uni-H class) given the highest priority by the class priority (SP) judgment left at destination port A. At destination ports B and C, multicast packets are selectable, and therefore, a multicast packet is selected by weighted round-robin.
Under this configuration, multicast packet readout requests for destination ports B and C are supplied to the multicast temporary buffer 50; however, the request for destination port A is not supplied to the temporary buffer 50. Accordingly, transmission of the multicast packet (PACKET i) is not completed within the prescribed time period set by the discard timer 14. The multicast packet (PACKET i) is discarded, causing undesirable packet loss.
It takes long time for the conventional multicast packet readout control method to transmit copies of the multicast packet stored in the multicast temporary buffer 50 to all the destinations if there is a destination with insufficient output bandwidth allocated among those destinations with a bit “1” set in the multicast destination bitmap.
Because the next multicast packet (PACKET ii) cannot be read from packet buffer 30 promptly, the subsequent multicast packets are being accumulated in the packet buffer 30. In spite of the fact that other destination ports are available, the next multicast packet (PACKET ii) cannot be transmitted to the destinations from said other ports. This causes serious delay due to blocking of multicast packets.
Blocking of multicast packets is caused by not only the existence of a destination with insufficient output bandwidth allocated, but also class priority (SP) control. In addition, with the conventional technique, packet loss occurs because the multicast packets delayed for a prescribed time period are discarded using a discard timer in order to start the readout process for the next multicast packet.
JP 2000-295256A discloses a technique for unicasting an APR (Address Resolution Protocol) request, which is generally transmitted by broadcasting, to reduce the network traffic. This technique is not addressed to readout control of multicast packets.